我的Bilibili频道：香芋派Taro
我的个人博客：taropie0224.github.io（阅读体验更佳）
我的公众号：香芋派的烘焙坊
我的音频技术交流群：1136403177
我的个人微信：JazzyTaroPie

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution
{
public:
    vector<int> plusOne(vector<int> &digits)
    {
        int n = digits.size();
        for (int i = n - 1; i >= 0; i--)
        {
            if (digits[i] != 9)
            {
                digits[i]++;
                for (int j = i + 1; j < n; j++)
                {
                    digits[j] = 0;
                }
                return digits;
            }
        }

        // digits 中所有的元素均为 9
        vector<int> ans(n + 1);
        ans[0] = 1;
        return ans;
    }
};

思路

首先可以分为三种情况：

  1. 例如[1, 2, 3]，这种最常规，只需要将数组的最后一个元素加一即可
  2. 例如[1, 2, 3, 9, 9, 9, 9]，从后向前遍历，找到第一个不是9的地方，然后把那个位置的元素加一，同时将后面的元素置0
  3. 例如[9, 9, 9, 9]，直接新建一个比原数组长度加一的数组，令第一个元素为1，后面的元素为0即可

上手：

  1. 从最后一个元素开始向前遍历数组
  2. 如果当前元素是9，那就跳过继续往前
  3. 如果当前元素不是9，把当前元素加一，把其后面的元素置0
  4. 以上已经包含了前两种情况，所以剩下的只可能是第三种情况